package hanjia;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Description:
 * Author:    Dane
 * CreateTime:2025/2/9-下午1:13
 * Since  :   1.0
 * Version:   1.0
 */
public class LeetCode111 {

    public int minDepth(TreeNode root) {
        if (root==null){
            return 0;
        }

     int d1=minDepth(root.left);
     int d2=minDepth(root.right);
     int result=Integer.MAX_VALUE;
     if (d1==0){
        return d2+1;
     }
     if (d2==0){
         return  d1+1;
     }


        return Math.min(d1,d2)+1;
    }

    public static int minDepth2(TreeNode root) {

        if (root==null){
            return 0;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.offer(root);
        int count=0;
        while (!queue.isEmpty()){
            int size=queue.size();
            for (int i=0;i<size;i++){
                TreeNode poll = queue.poll();
                if (poll.left==null&&poll.right==null){
                    return count+1;
                }
                if (poll.left!=null){
                    queue.offer(poll.left);

                }
                if (poll.right != null) {
                    queue.offer(poll.right);
                }


            }
            count++;


        }
        return count;


    }

    public static void main(String[] args) {
        Integer[] arr = {3, 9, 20, null, null, 15, 7};

        TreeNode root = buildTree(arr);
        minDepth2(root);
    }
    public static TreeNode buildTree(Integer[] arr) {
        if (arr == null || arr.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(arr[0]);
        java.util.LinkedList<TreeNode> queue = new java.util.LinkedList<>();
        queue.add(root);
        int index = 1;
        while (!queue.isEmpty() && index < arr.length) {
            TreeNode node = queue.poll();
            if (arr[index] != null) {
                node.left = new TreeNode(arr[index]);
                queue.add(node.left);
            }
            index++;
            if (index < arr.length && arr[index] != null) {
                node.right = new TreeNode(arr[index]);
                queue.add(node.right);
            }
            index++;
        }
        return root;
    }



}
